package DoublePointer;

import org.junit.Test;

import java.util.Stack;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: DoublePointer
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-11-03  18:57
 * @Description: TODO
 * @Version: 1.0
 */
public class 包含退格的字符串844 {

    public String buildString(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && s.charAt(i) == '#') {
                stack.pop();
                continue;
            }
            if (stack.isEmpty() && s.charAt(i) == '#') {
                continue;
            }
            stack.push(s.charAt(i));
        }
        String result = "";
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        return result;
    }

    public boolean backspaceCompare(String s, String t) {
        return buildString(s).equals(buildString(t));
    }

    // 一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
    // 具体地，我们定义 skip表示当前待删除的字符的数量。每次我们遍历到一个字符： 若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；
    // 若该字符为普通字符： 若 skip 为 0，则说明当前字符不需要删去； 若 skip不为 0，则说明当前字符需要删去，我们让skip减1。

    // 真实的就是比较skip==0 && s.chartAt(i) ！= skip==0 && s.chartAt(j)  return fasle  else true
    public boolean backspaceCompare2(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }

    public boolean backspaceCompare3(String s, String t) {
        int i = s.length() - 1, j = t.length() - 1;
        int skip1 = 0, skip2 = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skip1++;
                    i--;
                } else if (skip1 > 0) {
                    i--;
                    skip1--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skip2++;
                    j--;
                } else if (skip2 > 0) {
                    j--;
                    skip2--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }


    @Test
    public void test() {
        boolean b = backspaceCompare("y#fo##f", "y#f#o##f");
        System.out.println(b);
    }
}
